package com.rr.middle;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhuangcanrun
 * @Date 2021/10/28/17:28
 * @description
 **/
/*
* https://leetcode-cn.com/problems/reordered-power-of-2/
* todo:解出来了但数据很不好看，有待优化
* */
public class ReorderedPowerOf2 {
    public boolean reorderedPowerOf2(int n) {
        List<Integer> digitals = getDigitals(n);
        int digitalNum = digitals.size();
        for (int i = 0; i < digitalNum; i++) {
            Integer integer = digitals.get(i);
            if (integer == 0) {
                continue;
            }
            if (generateNumAndCheck(0, i, digitals)) {
                return true;
            }
        }
        return false;
    }

    private List<Integer> getDigitals(Integer num) {
        List<Integer> digitals = new ArrayList<Integer>();
        while (num > 0) {
            int i = num / 10;
            digitals.add(num - 10 * i);
            num /= 10;
        }
        return digitals;
    }

    private boolean generateNumAndCheck(Integer currentNum, Integer index, List<Integer> releaseDigital) {
        Integer appendNum = releaseDigital.get(index);
        currentNum = currentNum * 10 + appendNum;
        if (releaseDigital.size() == 1) {
            return checkIsPowBy2(currentNum);
        }
        List<Integer> newReleasedDigitals = new ArrayList<Integer>(releaseDigital);
        newReleasedDigitals.remove(appendNum);
        int length = newReleasedDigitals.size();
        for (int i = 0; i < length; i++) {
            if (generateNumAndCheck(currentNum, i, newReleasedDigitals)) {
                return true;
            }
        }
        return false;
    }

    private boolean checkIsPowBy2(Integer num) {
        int current = 1;
        while (true) {
            if (num == current) {
                return true;
            }
            int newCurrent = current * 2;
            if (num > current && num < newCurrent) {
                return false;
            }
            current = newCurrent;
        }
    }

    public static void main(String[] args) {
        ReorderedPowerOf2 reorderedPowerOf2 = new ReorderedPowerOf2();
        System.out.println(reorderedPowerOf2.reorderedPowerOf2(1));
    }
}
